package DataStructureAndAlgorithm.Acwing.DP.背包问题DP.多重背包DP;
import java.util.Scanner;
//多重背包问题
/*
状态描述：dp[i][j]：表示所有从前i种物品中选，并且总体积不超过j的选法
状态属性：max
状态方程：dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - k * v[i]] + k * w[i]);
*/
//未优化版本
public class dp_1019 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();//物品种类数
        int m = in.nextInt();//背包体积
        int[] w = new int[n + 1];//即物品的重量
        int[] v = new int[n + 1];//即物品的体积
        int[] s = new int[n + 1];//即物品的限制条件
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
            s[i] = in.nextInt();
        }
        //先枚举从前i个物品中选
        for (int i = 1; i <= n; i++){
            //再枚举前i个物品中选，体积为j的所有选法中能选的价值最大的方案
            for (int j = 1; j <= m; j++){
                //最后枚举限制条件，即第i个物品选几个的问题
                for (int k = 0; k <= s[i] && k * v[i] <= j; k++){
                    //注意：当k = 0时，dp[i - 1][j - k * v[i]] + k * w[i]对应的是不选第i种物品的情况
                    dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - k * v[i]] + k * w[i]);
                }
            }
        }
        //最后，根据状态定义，输出结果即可
        System.out.print(dp[n][m]);
    }
}



//优化版本
// import java.util.Scanner;
//
// class dp_1019{
//     public static void main(String[] args){
//         Scanner in = new Scanner(System.in);
//         int n = in.nextInt();//物品种类数
//         int m = in.nextInt();//背包体积
//         int[] w = new int[n + 1];//即物品的重量
//         int[] v = new int[n + 1];//即物品的体积
//         int[] s = new int[n + 1];//即物品的限制条件
//         int[] dp = new int[m + 1];
//         for (int i = 1; i <= n; i++){
//             v[i] = in.nextInt();
//             w[i] = in.nextInt();
//             s[i] = in.nextInt();
//         }
//         //先枚举从前i个物品中选
//         for (int i = 1; i <= n; i++){
//             //再枚举前i个物品中选，体积为j的所有选法中能选的价值最大的方案
//             //一维优化的时候，体积从大到小枚举，可以保证当前用到的结果，都是上一次循环中的结果
//             for (int j = m; j >= 0; j--){
//                 //最后枚举限制条件，即第i个物品选几个的问题
//                 for (int k = 0; k <= s[i] && k * v[i] <= j; k++){
//                     //注意：当k = 0时，dp[i - 1][j - k * v[i]] + k * w[i]对应的是不选第i种物品的情况
//                     dp[j] = Math.max(dp[j],dp[j - k * v[i]] + k * w[i]);
//                 }
//             }
//         }
//         //最后，根据状态定义，输出结果即可
//         System.out.print(dp[m]);
//     }
// }

/*
为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。

期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。
输入格式

第一行二个数n，m，其中n代表希望购买的奖品的种数，m表示拨款金额。

接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可）。
输出格式

一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。
数据范围

n≤500,m≤6000
,
v≤100,w≤1000,s≤10

输入样例：

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

输出样例：

1040

 */